import java.util.*;

// AI player
abstract class AI {
    protected final Map map;
    protected Game game;
    protected int[] monsterPos, roguePos;

    public AI(Map map, Game game) {
        this.map = map;
        this.game = game;
    }

    // Method to check if the LinkedList contains an int[] with the same content
    public static boolean containsArray(LinkedList<int[]> list, int[] target) {
        for (int[] arr : list) {
            if (Arrays.equals(arr, target)) {
                return true;
            }
        }
        return false;
    }

    // polymorphism
    public abstract int[] move();

    // move randomly
    protected int[] randomMove(int[] position) {
        LinkedList<int[]> possibleMoves = map.getNeighbors(position);
        return positionToMove(position, possibleMoves.get((int) (Math.random() * possibleMoves.size())));
    }

    public void updatePos() {
        monsterPos = game.getMonsterPos();
        roguePos = game.getRoguePos();
    }

    // helper methods for A star algorithm:
    // three distance methods
    private int manhattan(int[] start, int[] end){
        int dx = Math.abs(start[0] - end[0]);
        int dy = Math.abs(start[1] - end[1]);
        return dx+dy;
    }

    private int chebyshev(int[] start, int[] end) {
        int dx = Math.abs(start[0] - end[0]);
        int dy = Math.abs(start[1] - end[1]);
        return Math.max(dx, dy);
    }

    private int heuristic(int[] start, int[] end) {
        int dx = Math.abs(start[0] - end[0]);
        int dy = Math.abs(start[1] - end[1]);
        int diagonal = Math.min(dx, dy);
        int straight = dx + dy;
        return straight + (diagonal - straight / 2);
    }

    private Node getLowestFCostNode(List<Node> nodeList) {
        Node lowestFCostNode = nodeList.get(0);
        for (Node node : nodeList) {
            if (((AStarNode) node).g + ((AStarNode) node).h < ((AStarNode) lowestFCostNode).g + ((AStarNode) lowestFCostNode).h) {
                lowestFCostNode = node;
            }
        }
        return lowestFCostNode;
    }

    protected int AStarLength(int[] from, int[] to, boolean diagonal) {
        return AStar(from, to, diagonal).size();
    }

    // return the shortest (orthogonal) path from start to end obtained from A* algorithm.
    public LinkedList<int[]> AStar(int[] start, int[] end, boolean diagonal) {
        return AStar(start, end, diagonal, map, "heuristic");
    }

    protected LinkedList<int[]> AStar(int[] start, int[] end, boolean diagonal, Map m, String distance) {
        AStarNode startNode = switch (distance) {
            case ("heuristic") -> new AStarNode(start, null, 0, heuristic(start, end));
            case ("manhattan") -> new AStarNode(start, null, 0, manhattan(start, end));
            case ("chebyshev") -> new AStarNode(start, null, 0, chebyshev(start, end));
            default -> {
                System.out.println("Invalid distance method.");
                yield null;
            }
        };
        AStarNode endNode = new AStarNode(end, null, 0, 0);
        return AStar(startNode, endNode, diagonal, m, distance);
    }

    protected LinkedList<int[]> AStar(AStarNode start, AStarNode end, boolean diagonal, Map m, String distance) {
        List<Node> openList = new LinkedList<>();
        List<Node> closedList = new LinkedList<>();

        openList.add(start);

        while (!openList.isEmpty()) {
            AStarNode currentNode = (AStarNode) getLowestFCostNode(openList);
            openList.remove(currentNode);
            closedList.add(currentNode);

            if (currentNode.equals(end)) {
                return reconstructPath(currentNode);
            }

            List<int[]> neighborPositions;
            if (diagonal) neighborPositions = m.getNeighbors(currentNode.position);
            else {
                neighborPositions = m.getOrthogonalNeighbors(currentNode.position);
            }

            for (int[] neighborPos : neighborPositions) {
                if (containsPosition(closedList, neighborPos)) {
                    continue;
                }

                AStarNode neighborNode = (AStarNode) getNode(openList, neighborPos);
                if (neighborNode == null) {
                    neighborNode = switch (distance) {
                        case ("heuristic") -> new AStarNode(neighborPos, currentNode,
                                currentNode.g + 1, heuristic(neighborPos, end.position));
                        case ("manhattan") -> new AStarNode(neighborPos, currentNode,
                                currentNode.g + 1, manhattan(neighborPos, end.position));
                        case ("chebyshev") -> new AStarNode(neighborPos, currentNode,
                                currentNode.g + 1, chebyshev(neighborPos, end.position));
                        default -> {
                            System.out.println("Invalid distance method.");
                            yield null;
                        }
                    };
                    openList.add(neighborNode);
                } else if (currentNode.g + 1 < neighborNode.g) {
                    neighborNode.g = currentNode.g + 1;
                    neighborNode.f = neighborNode.g + neighborNode.h;
                    neighborNode.parent = currentNode;
                }
            }
        }
        return new LinkedList<>();
    }

    // return the shortest path from start to end using bfs. if there are multiple shortest paths, merge them into area.
    private LinkedList<Node> areaOfShortestPaths(int[] start, int[] end, Map m) {
        LinkedList<Node> frontiers = new LinkedList<>();
        LinkedList<Node> nextFrontiers = new LinkedList<>();
        LinkedList<Node> closed = new LinkedList<>();

        bfsNode root = new bfsNode(start);
        frontiers.add(root);
        closed.add(root);

        boolean found = false;

        while (!frontiers.isEmpty()) {
            for (Node current : frontiers) {
                for (int[] neighbor : m.getNeighbors(current.position)) {
                    if (!containsPosition(frontiers, neighbor) && !containsPosition(closed, neighbor)) {
                        if (containsPosition(nextFrontiers, neighbor)) {
                            ((bfsNode) getNode(nextFrontiers, neighbor)).parents.add((bfsNode) current);
                        } else {
                            bfsNode node = new bfsNode(neighbor, (bfsNode) current);
                            nextFrontiers.add(node);
                        }
                    }
                    if (Arrays.equals(neighbor, end)) {
                        found = true;
                    }
                }
            }
            if (found) break;

            closed.addAll(frontiers);
            frontiers = nextFrontiers;
            nextFrontiers = new LinkedList<>();
        }

        LinkedList<Node> area = new LinkedList<>();
        frontiers.clear();
        frontiers.add(getNode(nextFrontiers, end));
        nextFrontiers.clear();

        while (!frontiers.isEmpty()) {
            for (Node current : frontiers) {
                for (bfsNode parent : ((bfsNode) current).parents) {
                    if (!containsPosition(area, current.position)) {
                        nextFrontiers.add(parent);
                    }
                }
                if (!area.contains(current)) area.add(current);
            }
            frontiers = nextFrontiers;
            nextFrontiers = new LinkedList<>();
        }

        return area.reversed();
    }


    // helper method of A* algorithm
    private LinkedList<int[]> reconstructPath(AStarNode endNode) {
        LinkedList<int[]> path = new LinkedList<>();
        AStarNode currentNode = endNode;
        while (currentNode != null) {
            path.add(currentNode.position);
            currentNode = currentNode.parent;
        }
        Collections.reverse(path);
        return path;
    }

    // use depth first search to return a cluster
    private LinkedList<Node> findWallCluster(Node root) {
        LinkedList<Node> cluster = new LinkedList<>();
        cluster.add(root);
        dfs(root, cluster);
        return cluster;
    }

    // dfs recursion helper method
    private void dfs(Node root, LinkedList<Node> list) {
        for (int[] wall : map.getWallNeighbors(root.position)) {
            if (!containsPosition(list, wall)) {
                Node node = new Node(wall);
                list.add(node);
                dfs(node, list);
            }
        }
    }

    // return all shortest loops
    protected LinkedList<LinkedList<int[]>> getLoops(LinkedList<Node> loopNodes) {
        LinkedList<LinkedList<int[]>> loops = new LinkedList<>();
        if (loopNodes != null) loopNodes.clear();

        // find all lands that are space/wall
        LinkedList<Node> spaceLand = new LinkedList<>();
        for (int i = 0; i < map.size(); i++) {
            for (int j = 0; j < map.size(); j++) {
                if (map.getType(i, j) == ' ') spaceLand.add(new Node(new int[]{i, j}));
            }
        }

        // obtain clusters of walls
        LinkedList<LinkedList<Node>> clusters = new LinkedList<>();
        while (!spaceLand.isEmpty()) {
            LinkedList<Node> cluster = findWallCluster(spaceLand.getFirst());
            spaceLand.removeAll(cluster);
            clusters.add(cluster);
        }

        // remove wall clusters that connects to boundary
        Iterator<LinkedList<Node>> clusterIter = clusters.iterator();
        while (clusterIter.hasNext()) {
            for (Node node : clusterIter.next()) {
                if (map.isBoundary(node.position)) {
                    clusterIter.remove();
                    break;
                }
            }
        }

        // find the shortest upper path and shortest lower path, connect to form the shortest loop
        for (LinkedList<Node> cluster : clusters) {
            int[] leftMost = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
            int[] rightMost = new int[]{Integer.MIN_VALUE, Integer.MIN_VALUE};
            for (Node land : cluster) {
                if (land.position[0] < leftMost[0]) leftMost = Arrays.copyOf(land.position, 2);
                if (land.position[0] > rightMost[0]) rightMost = Arrays.copyOf(land.position, 2);
            }
            leftMost[0] -= 1; // left land position left to the leftmost wall
            rightMost[0] += 1; // right most land

            // find the shortest upper loop
            Map upperMap = map.copy();
            for (int i = 0; i < leftMost[0]; i++)
                upperMap.setLand(i, leftMost[1], ' ');
            for (int i = -1; i <= 1; i++)
                upperMap.setLand(leftMost[0] + i, leftMost[1] - 1, ' ');

            for (int i = rightMost[0] + 1; i < upperMap.size(); i++)
                upperMap.setLand(i, rightMost[1], ' ');
            for (int i = -1; i <= 1; i++)
                upperMap.setLand(rightMost[0] + i, rightMost[1] - 1, ' ');

            loops.add(AStar(leftMost, rightMost, true, upperMap, "heuristic")); // add to result
            loops.getLast().removeFirst(); // remove leftmost point
            loops.getLast().removeLast(); // remove rightmost point

            if (loopNodes != null) {
                loopNodes.addAll(areaOfShortestPaths(leftMost, rightMost, upperMap));
                loopNodes.removeFirst();
                loopNodes.removeLast();
            }

            // shortest lower loop
            Map lowerMap = map.copy();
            for (int i = 0; i < leftMost[0]; i++)
                lowerMap.setLand(i, leftMost[1], ' ');
            for (int i = -1; i <= 1; i++)
                lowerMap.setLand(leftMost[0] + i, leftMost[1] + 1, ' ');

            for (int i = rightMost[0] + 1; i < upperMap.size(); i++)
                lowerMap.setLand(i, rightMost[1], ' ');
            for (int i = -1; i <= 1; i++)
                lowerMap.setLand(rightMost[0] + i, rightMost[1] + 1, ' ');

            loops.getLast().addAll(AStar(leftMost, rightMost, true, lowerMap, "heuristic"));
            if (loopNodes != null) loopNodes.addAll(areaOfShortestPaths(leftMost, rightMost, lowerMap));
        }

        // Special case: 2x2 block of connected rooms and corridors form a small loop
        for (int i = 0; i < map.size() - 1; i++) {
            for (int j = 0; j < map.size() - 1; j++) {

                // for each 2x2 block
                int roomCount = 0;
                for (int x = 0; x < 2 && roomCount >= 0; x++) {
                    for (int y = 0; y < 2 && roomCount >= 0; y++) {
                        if (map.getType(i + x, j + y) == ' ') // contains space
                            roomCount = -1; // not a loop
                        if (map.getType(i + x, j + y) == '.') roomCount++;
                    }
                }
                if (roomCount == -1) continue;

                // exclude not matched cases
                if (roomCount > 2) continue;
                if (roomCount == 2) {
                    if (map.getType(i, j + 1) == '.' && map.getType(i + 1, j) == '.' || map.getType(i, j)
                            == '.' && map.getType(i + 1, j + 1) == '.') {
                        continue;
                    }
                }

                // add small loop
                loops.add(new LinkedList<>());
                for (int x = 0; x < 2; x++) {
                    for (int y = 0; y < 2; y++) {
                        loops.getLast().add(new int[]{i + x, j + y});
                        loopNodes.add(new bfsNode(new int[]{i + x, j + y}));
                    }
                }
            }
        }

        return loops;
    }

    // Breadth first double search: two-root version of bfs, one root would occupy the other's land
    // If any loop is fully reachable, return the index of the first such loop. Stored the progress in record.
    protected int bfds(List<LinkedList<int[]>> loopsOfTargets, List<LinkedList<int[]>> record) {
        return bfds(loopsOfTargets, record, null, null);
    }

    // Also, store the path to the first reached land in a loop that must be visited by rogue in pathToDoor
    protected int bfds(List<LinkedList<int[]>> loopsOfTargets, List<LinkedList<int[]>> record,
                       LinkedList<Node> bfsNodes, LinkedList<int[]> pathToDoor) {
        LinkedList<Node> monsterClosed = new LinkedList<>();
        LinkedList<Node> monsterFrontier = new LinkedList<>(); // monster's current frontier
        LinkedList<Node> monsterNextFrontier = new LinkedList<>(); // monster's frontier for next step
        LinkedList<Node> rogueClosed = new LinkedList<>();
        LinkedList<Node> rogueFrontier = new LinkedList<>(); // rogue's
        LinkedList<Node> rogueNextFrontier = new LinkedList<>();

        int index = -1; // index of the first reachable loop
        bfsNode door = null; // the first reached land in a loop that is between an open space and a corridor

        monsterFrontier.add(new bfsNode(monsterPos));
        rogueFrontier.add(new bfsNode(roguePos));

        // main recursion:
        while (!rogueFrontier.isEmpty()) {
            // rogue expand
            for (Node currentFrontier : rogueFrontier) {
                for (int[] neighbor : map.getNeighbors(currentFrontier.position)) { // for each neighbor of current land

                    // continue if this land has been covered
                    if (containsPosition(rogueClosed, neighbor) || containsPosition(rogueFrontier, neighbor) ||
                            containsPosition(rogueNextFrontier, neighbor) || containsPosition(monsterFrontier, neighbor))
                        continue;

                    rogueNextFrontier.add(new bfsNode(neighbor, (bfsNode) currentFrontier)); // add land to next step of frontier

                    // if this land is on a loop and must be visited by the rogue
                    for (int loopIndex = 0; loopIndex < loopsOfTargets.size() && door == null; loopIndex++) { // traverse each loop
                        for (int[] loopPos : loopsOfTargets.get(loopIndex)) { // each land on loop
                            if (Arrays.equals(neighbor, loopPos) && ((bfsNode) getNode(bfsNodes, neighbor)).must) { // if this land reaches any door on loop
                                door = (bfsNode) getNode(rogueNextFrontier, neighbor);
                                index = loopIndex;

                                break;
                            }
                        }
                    }
                }
            }

            if (record != null) { // store progress in record
                record.add(new LinkedList<>());
                for (Node node : rogueFrontier) {
                    record.getLast().add(node.position);
                }
            }
            rogueClosed.addAll(rogueFrontier); // these frontier lands have been covered.
            rogueFrontier = rogueNextFrontier;
            rogueNextFrontier = new LinkedList<>();

            // monster expand
            for (Node currentFrontier : monsterFrontier) {
                for (int[] neighbor : map.getNeighbors(currentFrontier.position)) { // for each neighbor of current land
                    if (!containsPosition(monsterClosed, neighbor) && !containsPosition(monsterFrontier, neighbor) &&
                            !containsPosition(monsterNextFrontier, neighbor)) {
                        monsterNextFrontier.add(new Node(neighbor)); // add land to next step of frontier

                        if (containsPosition(rogueFrontier, neighbor)) // Occupy Rogue's land
                            rogueFrontier.remove(new Node(neighbor));
                    }
                }
            }
            monsterClosed.addAll(monsterFrontier); // these frontier lands have been covered.
            monsterFrontier = monsterNextFrontier;
            monsterNextFrontier = new LinkedList<>();
        }

        if (pathToDoor != null) {
            LinkedList<int[]> path = new LinkedList<>();
            if (door != null) {
                bfsNode current = door;
                while (true) {
                    path.add(current.position);
                    if (current.parents.isEmpty()) break;
                    current = current.parents.getFirst();
                }
                path.removeLast();
                pathToDoor.addAll(path.reversed());
            }
        }
        return index; // no reachable loop found
    }

    // convert a position on map to the direction for character's next movement
    protected int[] positionToMove(int[] from, int[] to) {
        return new int[]{Integer.compare(to[0], from[0]), Integer.compare(to[1], from[1])};
    }

    // check if a list of nodes contains a land with the same position
    protected boolean containsPosition(List<Node> nodeList, int[] position) {
        for (Node node : nodeList) {
            if (Arrays.equals(node.position, position)) {
                return true;
            }
        }
        return false;
    }

    // get the node with the same position from a list of nodes
    protected Node getNode(List<Node> nodeList, int[] position) {
        for (Node node : nodeList) {
            if (Arrays.equals(node.position, position)) {
                return node;
            }
        }
        return null;
    }

}